package datastructure.tree;

import java.util.Comparator;

/**
 * @Description: 平衡二叉搜索树
 * @Author Ammar
 * @Create 2023/4/17 17:27
 */
public class BalaceBinarySearchTree<E> extends BinarySearchTree<E> {

    public BalaceBinarySearchTree() {
        super(null);
    }

    public BalaceBinarySearchTree(Comparator<E> comparator) {
        super(comparator);
    }



    protected void rotateLeft(TreeNode<E> grand) {
        TreeNode<E> parent = grand.right;
        TreeNode<E> leftChild = parent.left;
        // 左旋转
        grand.right = leftChild;
        parent.left = grand;
        // 更新 parent 的 parent
        afterRotate(grand, parent, leftChild);
    }

    protected void rotateRight(TreeNode<E> grand) {
        TreeNode<E> parent = grand.left;
        TreeNode<E> rightChild = parent.right;
        // 右旋转
        grand.left = rightChild;
        parent.right = grand;
        afterRotate(grand, parent, rightChild);
    }

    protected void afterRotate(TreeNode<E> grand, TreeNode<E> parent, TreeNode<E> child) {
        // 让 parent 成为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            root = parent;
        }

        // 更新 child 的 parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新 grand 的 parent
        grand.parent = parent;
    }

    protected void rotate(
            TreeNode<E> r, // 子树的根节点
            TreeNode<E> a, TreeNode<E> b, TreeNode<E> c,
            TreeNode<E> d,
            TreeNode<E> e, TreeNode<E> f, TreeNode<E> g) {
        // 让 d 成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // a b c
        b.left = a;
        b.right = c;
        if (a != null) a.parent = b;
        if (c != null) c.parent = b;

        // e f g
        f.left = e;
        f.right = g;
        if (e != null) e.parent = f;
        if (g != null) g.parent = f;

        // b d f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
    }
}
